// tspcluster - Traveling Salesman Problem
// Copyright (C) 2006  Frederik Carlier
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA

using System;
using System.Diagnostics;

namespace UGent.Tsp
{
    public class RandomPermutation
    {
        public RandomPermutation(int seed)
            : this(new Random(seed))
        {
        }
        
        public RandomPermutation()
            : this(new Random())
        {
        }

        public RandomPermutation(Random random)
        {
            this.random = random;
        }

        Random random;

        // Gets a random permuation of n letters (0..n)
        public int[] Next(int n)
        {
            int[] permutation = new int[n];
            for (int i = 0; i < n; i++)
                permutation[i] = i;

            int temp;
            int l;
            for (int m = 0; m < n; m++)
            {
                // Choose l random between [m,n]
                l = random.Next(m, n);
                temp = permutation[l];
                permutation[l] = permutation[m];
                permutation[m] = temp;
            }

            return permutation;
        }

        public static void RunOnConsole()
        {
            RandomPermutation randomPermutation = new RandomPermutation();
            int n = 10;

            // Speed test
            Stopwatch watch = new Stopwatch();
            watch.Start();
            for (int i = 0; i < 500000; i++)
                randomPermutation.Next(n);
            watch.Stop();

            Console.WriteLine(watch.ElapsedMilliseconds);
            Console.ReadLine();

            while (true)
            {
                int[] permutation = randomPermutation.Next(n);
                for (int i = 0; i < n; i++)
                    Console.Write(permutation[i].ToString() + " ");
                Console.WriteLine();
            }
        }
    }
}